﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MyLibrary
{
    public static class Algorithms
    {
        /// <summary>
        /// 对指定的字符串预处理，预处理结果可用于KmpMatch。
        /// 若该pattern要多次与其他对象比对，应考虑调用此方法，避免每次都预处理。
        /// </summary>
        /// <param name="pattern"></param>
        /// <returns></returns>
        public static int[] KmpPreprocess(string pattern)
        {
            int[] failPosition = new int[pattern.Length];
            failPosition[0] = -1;
            int j = -1;//将要放入failPosition的数值
            for (int i = 1; i < pattern.Length; i++)
            {
                while (j > -1 && pattern[j + 1] == (pattern[i]) == false)
                { j = failPosition[j]; }
                if (pattern[j + 1] == (pattern[i]))
                    j = j + 1;
                failPosition[i] = j;
            }
            return failPosition;
        }

        public static void KmpMatch<TSource>(TSource source, string pattern, Func<TSource, Tuple<bool, char>> next, int[] preprocessResult = null)
        {
            if (preprocessResult == null)
                preprocessResult = KmpPreprocess(pattern);
            int j = 0;
            Tuple<bool, char> n;
            while ((n = next(source)).Item1)
            {
                while (j > -1 && pattern[j + 1] != n.Item2)
                { j = preprocessResult[j]; }
                if (pattern[j + 1] == n.Item2)
                    j = j + 1;
                if (j == pattern.Length - 1)
                {
                    //Console.WriteLine(source);
                    //Console.WriteLine(new string(' ', i - pattern.Length + 1) + pattern);
                    return;
                    j = preprocessResult[j];
                }
            }
        }

        public static int[] KmpPreprocess<TElement>(TElement[] pattern) where TElement : IEquatable<TElement>
        {
            int[] failPosition = new int[pattern.Length];
            failPosition[0] = -1;
            int j = -1;//将要放入failPosition的数值
            for (int i = 1; i < pattern.Length; i++)
            {
                while (j > -1 && pattern[j + 1].Equals(pattern[i]) == false)
                { j = failPosition[j]; }
                if (pattern[j + 1].Equals(pattern[i]))
                    j = j + 1;
                failPosition[i] = j;
            }
            return failPosition;
        }

        /// <summary>
        /// 进行KMP匹配。
        /// <para>source中可以获得TElement类型的数据，而pattern正是TElement的数组。本方法寻找出pattern对应source中的哪个位置。</para> 
        /// <para>匹配的位置由moveNext隐式提供，moveNext应自己记住位置。当方法返回时，moveNext记住的位置是“source开始匹配的位置+pattern的长度”。</para> 
        /// </summary>
        /// <typeparam name="TSource"></typeparam>
        /// <typeparam name="TElement"></typeparam>
        /// <param name="source"></param>
        /// <param name="pattern"></param>
        /// <param name="next">将source前进一个位置，并返回在新位置的元素的方法。第一分量true表示已经前进了一个位置。</param>
        /// <param name="preprocessResult">预处理结果</param>
        public static void KmpMatch<TSource, TElement>(TSource source, TElement[] pattern, Func<TSource, Tuple<bool, TElement>> next, int[] preprocessResult = null) where TElement : IEquatable<TElement>
        {
            if (preprocessResult == null)
                preprocessResult = KmpPreprocess(pattern);
            int j = 0;
            Tuple<bool, TElement> n;
            while ((n = next(source)).Item1)
            {
                while (j > -1 && pattern[j + 1].Equals(n.Item2) == false)
                { j = preprocessResult[j]; }
                if (pattern[j + 1].Equals(n.Item2))
                    j = j + 1;
                if (j == pattern.Length - 1)
                {
                    //Console.WriteLine(source);
                    //Console.WriteLine(new string(' ', i - pattern.Length + 1) + pattern);
                    return;
                    j = preprocessResult[j];
                }
            }
        }

        public static void KmpMatch<TElement>(IEnumerable<TElement> source, TElement[] pattern, int[] preprocessResult = null) where TElement : IEquatable<TElement>
        {

            if (preprocessResult == null)
                preprocessResult = KmpPreprocess(pattern);
            int j = 0;

            foreach (TElement element in source)
            {
                while (j > -1 && pattern[j + 1].Equals(element) == false)
                { j = preprocessResult[j]; }
                if (pattern[j + 1].Equals(element))
                    j = j + 1;
                if (j == pattern.Length - 1)
                {
                    //Console.WriteLine(source);
                    //Console.WriteLine(new string(' ', i - pattern.Length + 1) + pattern);
                    return;
                    j = preprocessResult[j];
                }
            }
        }
    }
}
